# !/usr/bin/env python3
# -*- coding: utf-8 -*-

# 希尔排序相当于在插入排序的基础上，进行改进，由每次一小步改为一大步
def shellSort(arr):
    # import math
    gap = len(arr)/3 + 1  # 间隔---步长
    # 动态定义间隔序列--当长度大于3的被数时，步长就不为1

    while gap > 0:
        # 插入排序--只是步长变了
        # print("gap: ", gap)
        for i in range(gap,len(arr)):
            choose = arr[i]
            preIndex = i-gap
            while preIndex >=0 and arr[preIndex] > choose:
                arr[preIndex+gap]=arr[preIndex]
                preIndex-=gap
            arr[preIndex+gap] = choose
        # gap = math.floor(gap/2)
        gap = gap/2   # 自动向下取整
    return arr



if __name__ == '__main__':
    arr = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70, 1, 2, 3, 42, 4, 234,0]
    arr = shellSort(arr)
    print(arr)